package com.practice.dp;

import java.util.Arrays;

/**
 * There is a straight roads with 'n' number of milestones. You are given an
 * array with the distance between all the pairs of milestones in some random
 * order. Find the position of milestones.
 * 
 * Example:
 * Consider a road with 4 milestones(a,b,c,d) :
 * a <--- 3Km --->b<--- 5Km --->c<--- 2Km --->d
 * Distance between a and b = 3
 * Distance between a and c = 8
 * Distance between a and d = 10
 * Distance between b and c = 5
 * Distance between b and d = 7
 * Distance between c and d = 2
 * 
 * All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
 * 
 * The output must be 3,5,2 or 2,5,3
 *
 */
public class Milestone {
	private int dfsCount = 0;

	public int[] findMilestones(int[] dists) {
		long t0 = System.currentTimeMillis();
		
		dfsCount = 0;
		
		int L = dists.length;
		int N = (int) ((Math.sqrt(1 + 8 * L) - 1) / 2);
		int[] founded = new int[N+1];
		int max = dists[dists.length - 1];
		int[] map = new int[max + 1];
		for (int i = 0; i < map.length; i++) {
			map[i] = 0;
		}
		for (int i = 0; i < dists.length; i++) {
			map[dists[i]]++;
		}
		int cur = dists.length - 1;
		search(founded, 0, dists, N, cur, map);

		int[] solution = new int[N];
		for (int i=0; i<N; i++) {
			solution[i] = founded[i] - founded[i+1];
		}
		
		long t1 = System.currentTimeMillis();
		System.out.println("DFS count = " + dfsCount + ", takes " + (t1-t0) + "ms.");
		return solution;
	}

	private boolean search(int[] founded, int len, int[] dists,
			int N, int cur, int[] map) {
		dfsCount++;
		if (len == N) return true;

		// Optimize the lower bound of the index for the next search nodes
		int nextMax = dists[cur];
		int delta = 0;
		if (len >= 2) {
			delta = founded[0] - founded[len-1];
		}
		int minPossible = nextMax - delta;
		int lb = 0;
		if (minPossible > 0) {
			lb = Math.abs(Arrays.binarySearch(dists, minPossible));
		}
		int remaining = N - len;

		lb = Math.max(remaining * (remaining + 1) / 2 - 1, lb - 1);
		for (int i = cur; i >= lb; i--) {
			int candidate = dists[i];
			while (i>=lb && candidate==dists[i-1]) i--;
			
			if (isCandidate(founded, len, candidate, map)) {
				founded[len] = candidate;
				if (search(founded, len+1, dists, N, i - 1, map)) {
					return true;
				}
				map[candidate]++;
				for (int j=0; j<len; j++) {
					map[founded[j] - candidate]++;
				}
			}
		}
		return false;
	}

	private boolean isCandidate(int[] founded, int len, int candidate, int[] map) {
		if (map[candidate] == 0) return false;
		map[candidate]--;
		for (int i=0; i<len; i++) {
			if (map[founded[i]-candidate] == 0) {	// revert
				map[candidate]++;
				for (int j=0; j<i; j++) {
					map[founded[j]-candidate]++;
				}
				return false;
			}
			else {
				map[founded[i]-candidate]--;
			}
		}
		return true;
	}
}
